In [ ]:
%%HTML
<style>
.container { width:100% }
</style>
The holy book of Taoism, the Tao Te Ching, contains the following wisdom:
Taoistic search is based on this principle:
We will use taoistic search to solve the search problem for the 15-puzzle where the states Start and Goal are defined
as follows.
In [ ]:
Start = ( ( '0', '14', '8', '12' ),
( '10', '11', '13', '9' ),
( '6', '2', '4', '15' ),
( '3', '5', '7', '1' )
)
In [ ]:
Goal = ( ( '0', '1', '2', '3' ),
( '4', '5', '6', '7' ),
( '8', '9', '10', '11' ),
( '12', '13', '14', '15' )
)
In order to view these states more conveniently, we define a number of auxiliary functions in the following subsection.
In [ ]:
import ipycanvas as cnv
The module time is part of the standard library so it is preinstalled. We have imported it because we need the function time.sleep(secs) to pause the animation for a specified time.
In [ ]:
import time
The global variable Colors specifies the colors of the tiles.
In [ ]:
Colors = ['white', 'lightblue', 'pink', 'magenta', 'orange', 'red', 'yellow', 'lightgreen', 'gold',
'CornFlowerBlue', 'Coral', 'Cyan', 'orchid', 'DarkSalmon', 'DeepPink', 'green'
]
The global variable size specifies the size of one tile in pixels.
In [ ]:
size = 100
The function draw(State, canvas, dx, dy, tile, x) draws a given State of the sliding puzzle, where tile has been moved by offset pixels into the direction (dx, dy).
In [ ]:
def draw(State, canvas, dx, dy, tile, offset):
canvas.text_align = 'center'
canvas.text_baseline = 'middle'
with cnv.hold_canvas(canvas):
canvas.clear()
n = len(State)
for row in range(n):
for col in range(n):
tile_to_draw = State[row][col]
if tile_to_draw != '*':
color = Colors[int(tile_to_draw)]
else:
color = 'lightyellow'
canvas.fill_style = color
if tile_to_draw not in ('0', tile):
x = col * size
y = row * size
canvas.fill_rect(x, y, size, size)
canvas.stroke_rect(x, y, size, size)
canvas.line_width = 3.0
x += size // 2
y += size // 2
canvas.stroke_text(str(tile_to_draw), x, y)
elif tile_to_draw == tile:
x = col * size + offset * dx
y = row * size + offset * dy
canvas.fill_rect(x, y, size, size)
canvas.stroke_rect(x, y, size, size)
canvas.line_width = 3.0
x += size // 2
y += size // 2
if tile_to_draw != 0:
canvas.stroke_text(str(tile_to_draw), x, y)
In [ ]:
def create_canvas(n):
canvas = cnv.Canvas(size=(size * n, size * n))
canvas.font = '60px serif'
return canvas
In [ ]:
def draw_state(State):
n = len(State)
canvas = create_canvas(n)
draw(State, canvas, 0, 0, '+', 0)
display(canvas)
The global variable delay controls the speed of the animation.
If the animation is jerky on your computer, try increasing the value of `delay`.
In [ ]:
delay = 0.002
The function call tile_and_direction(state, next_state) takes a state and the state that follows this state and returns a triple (tile, dx, dy) where tileis the tile that is moved to transform state into next_state and (dx, dy) is the direction in which this tile is moved.
In [ ]:
def tile_and_direction(state, next_state):
row0, col0 = find_tile('0', state)
row1, col1 = find_tile('0', next_state)
return state[row1][col1], col0-col1, row0-row1
Given a list of states representing a solution to the sliding puzzle, the function call
animation(Solution) animates the solution.
In [ ]:
def animation(Solution):
start = Solution[0]
n = len(start)
canvas = create_canvas(n)
draw(start, canvas, 0, 0, 0, 0)
m = len(Solution)
display(canvas)
for i in range(m-1):
state = Solution[i]
tile, dx, dy = tile_and_direction(state, Solution[i+1])
for offset in range(size+1):
draw(state, canvas, dx, dy, tile, offset)
time.sleep(delay)
Let us begin by our explanation by drawing both the states Start and Goal of our search problem.
In [ ]:
draw_state(Start)
In [ ]:
draw_state(Goal)
In order to solve this instance of the 15-puzzle we could start by moving the tiles 14 and 15 into their final destination
without caring for the other tiles. To this end we define two new extended states Start1 and Goal1 as shown below. In these extended states we have replaced all those tiles that are not important for moving 14 and 15 into their final destination by wildcard tiles defined as '*'.
Extended states are also known as patterns.
In [ ]:
Start1 = ( ( '0', '14', '*', '*' ),
( '*', '*', '*', '*' ),
( '*', '*', '*', '15' ),
( '*', '*', '*', '*' )
)
draw_state(Start1)
In [ ]:
Goal1 = ( ( '*', '*', '*', '*' ),
( '*', '*', '*', '*' ),
( '*', '*', '*', '*' ),
( '*', '*', '14', '15' )
)
draw_state(Goal1)
It should be noted that we have replaced the tile numbered '0' by a wildcard tile '*' when creating the state Goal1, but
not when creating the state Start1. The reason is es explained below.
The search problem specified by Start1 and Goal1 is quite easy to solve. We remember the set of
actions, i.e. movements
of the empty tile that we had to perform to transform Start1 into Goal1. Next, we apply these actions to the state Start. The resulting state might look like the state State shown below.
Now we can explain the reason for not replacing the empty tile with '*' in Start1 since otherwise we would not be able to
use the actions found when to transforming Start1 to Goal1 to transform the state Start1 into the state State.
In [ ]:
State = ( ('10', '8', '13', '12'),
('11', '5', '2', '9'),
( '6', '7', '0', '4'),
( '3', '1', '14', '15')
)
draw_state(State)
Our next goal is move the tiles numbered with 12 and 13 into their final position. To this end we define the
extended states Start2 and Goal2 as shown below.
In [ ]:
Start2 = ( ( '*', '*', '13', '12' ),
( '*', '*', '*', '*' ),
( '*', '*', '0', '*' ),
( '*', '*', '14', '15' )
)
draw_state(Start2)
In [ ]:
Goal2 = ( ( '*', '*', '*', '*'),
( '*', '*', '*', '*'),
( '*', '*', '*', '*'),
('12', '13', '14', '15')
)
draw_state(Goal2)
Again, we solve the resulting search problem and remember the actions that transformed Start2 into Goal2. We apply these actions to the state State and end up with Statebeing transformed into the state shown below.
In [ ]:
State = ( ('10', '5', '8', '9'),
( '6', '11', '7', '4'),
( '1', '3', '0', '2'),
('12', '13', '14', '15')
)
draw_state(State)
Proceeding in this way we can solve the given instance of the 15-puzzle. The solution that we find will not be optimal but it won't be too far from the optimal solution.
The function call find_tile(tile, State) finds the coordinates of the given tile in State. The tile is represented as a string from the set
{'0', '1', ..., '15'},
where '0' represents the empty tile.
Nota bene:
We have to represent the tiles as strings instead of numbers as we will later replace some of these tiles by the wildcard
character '*'. The class Set that we use to represent sets of states does not permit inhomogeneous sets, i.e. sets that
contain both numbers and strings.
The parameter State is a tuple of tuples that specifies the positions of the tiles. If (row, col) is the result returned by find_tile, then we have:
State[row][col] == tile
In [ ]:
def find_tile(tile, State):
n = len(State)
for row in range(n):
for col in range(n):
if State[row][col] == tile:
return row, col
Since A$^*$-search stores the set of states that have been visited, we have to represent states by immutable objects and hence we represent the states as tuples of tuples. In order to be able to change these states, we have to transform these tuples of tuples into lists of lists. The function to_list transforms a tuple of tuples into a list of lists.
In [ ]:
to_list = lambda State: [list(row) for row in State]
The function to_tuple transforms a list of lists into a tuple of tuples.
In [ ]:
to_tuple = lambda State: tuple(tuple(row) for row in State)
Given a State that satisfies
State[row][col] == '0'and a direction (dx, dy) that is an element form the set
$\bigl\{ (1, 0), (-1, 0), (0, 1), (0, -1) \bigr\}$,
the function move_dir moves the empty tile in the direction (dx, dy).
In [ ]:
def move_dir(State, row, col, dx, dy):
State = to_list(State)
State[row ][col ] = State[row + dx][col + dy]
State[row + dx][col + dy] = '0'
return to_tuple(State)
Given a State of the sliding puzzle, the function next_states(State) computes all those states that can be reached from State in one step.
In [ ]:
def next_states(State):
n = len(State)
row, col = find_tile('0', State)
NewStates = set()
Directions = [ (1, 0), (-1, 0), (0, 1), (0, -1) ]
for dx, dy in Directions:
if row + dx in range(n) and col + dy in range(n):
NewStates.add(move_dir(State, row, col, dx, dy))
return NewStates
The function matches(Pattern, State) checks, whether the pattern Pattern matches the state State. A pattern is like a state but instead of numbers, some of the entries of the list of lists are the
string *. The idea is that * is a wildcard that matches anything.
Note that State can also be an extended state.
In [ ]:
def matches(Pattern, State):
"your code here"
The function manhattan implemented below takes as argument two extended states State1 and State2
possibly containing wildcards and computes the Manhattan distance between these
extended states. Basically, the manhattan distance measure the number of moves that it would take to transform stateA into stateB if we were allowed to slide different tiles on top of each other.
When computing these distances, tiles that are numbered with a wildcard are ignored.
In [ ]:
def manhattan(State1, State2):
"your code here"
The function find_tiles takes a pattern Pattern as input and returns the
list of all tiles in Pattern that are labeled with a number.
In [ ]:
def find_tiles(Pattern):
Result = []
n = len(Pattern)
for row in range(n):
for col in range(n):
tile = Pattern[row][col]
if tile != '*':
Result.append(tile)
return Result
The function replace_numbers takes two arguments:
Pattern is an extended state,Tiles is a list of numbered tiles.
The state Pattern is transformed by replacing all tiles that are not a member of the list Tiles
with the wildcard character *.
In [ ]:
def replace_numbers(Pattern, Tiles):
"your code here"
The function intermediate_goals is called with two parameters:
Goal is a state of the 15-puzzle,TilesList is a list of list of numbers.
For example, TilesList could be the list [ [14, 15], [12, 13] ].
This list would specify that we want to create two intermediate
goals. 14and 15,
while all other tiles would be replaced by wildcards.12, 13, 14,
and 15, while all other tiles would be replaced by wildcards.The function returns the list of intermediate goals.
In [ ]:
def intermediate_goals(Goal, TilesList):
"your code here"
Given two extended states Pattern1 and Pattern2 the function extract_move returns a pair (dx, dy) such that we have:
(row, col) = find_tile('0', Pattern1) -> move_dir(Pattern1, row, col, dx, dy) == Pattern2Hence extract_move(Pattern1, Pattern2) computes the action that is necessary to transform Pattern1 into
Pattern2. This action is encoded as a direction (dx, dy). This is the direction to move the empty tile in Pattern1 to reach Pattern2.
In [ ]:
def extract_move(Pattern1, Pattern2):
"your code here"
Given a list of extended states PatternList of the form
$$ \texttt{PatternList} = [P_1, P_2, \cdots, P_n] $$
the function extract_move_list computes a list of actions $[a_1, a_2, \cdots, a_{n-1}]$ such that
applying action $(a_i)$ to state $P_i$ results in state $P_{i+1}$.
The actions are pairs of the form (dx, dy) that specify how the empty tile is to be moved.
In [ ]:
def extract_move_list(PatternList):
"your code here"
Given the list of actions MoveList of the form $[a_1, a_2, \cdots, a_{n-1}]$, the function
apply_move_list takes a state State and applies these action to Stateone by one. The list of all
states produced this way is returned. This list starts with the given state State.
In [ ]:
def apply_move_list(State, MoveList):
"your code here"
The function stateToString is useful for debugging purposes to transform a given state into a string.
In [ ]:
def stateToString(state):
n = len(state)
indent = " " * 4;
line = indent + "+---" * n + "+\n"
result = line
for row in range(n):
result += indent + "|"
for col in range(n):
cell = state[row][col]
if isinstance(cell, str) and cell != '*':
cell = int(cell)
if cell == "*":
result += " * "
elif cell >= 10:
result += str(cell) + " "
elif cell > 0 and cell < 10:
result += " " + str(cell) + " "
else:
result += " "
result += "|"
result += "\n"
result += line
return result
The module Set implements sets as
AVL trees.
The API provided by Set offers the following functions and methods:
Set() creates an empty set.S.isEmpty() checks whether the set Sis empty.S.member(x) checks whether x is an element of the set S.S.insert(x) inserts x into the set S.
This does not return a new set but rather modifies the set S.S.delete(x) deletes x from the set S.
This does not return a new set but rather modifies the set S.S.pop() returns the smallest element of the set S.
Furthermore, this element is removed from S.
Since sets are implemented as ordered binary trees, the elements of a set need to be comparable, i.e. if x and y are inserted into a set, then the
expression x < y must return a Boolean value and < has to define
linear order.The module Set can be used to implement a priority queue that supports the removal of elements.
In [ ]:
import Set
The function search takes three arguments to solve a search problem:
Start is the start state of the search problem.Goalis the goal state. This might be an extended state.next_states is a function with signature $\texttt{next_states}:Q \rightarrow 2^Q$, where $Q$ is the set of states.
For every state $s \in Q$, $\texttt{next_states}(s)$ is the set of states that can be reached from $s$ in one step.heuristic is a function that takes two states as arguments. It returns an estimate of the
length of the shortest path between these states.
If successful, search returns a path from start to goal that is a solution of the search problem
$$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle. $$Basically, the function search implements A$^*$ search, but instead of checking whether a state is identical to Goal, this function only tests whether a state matches goal.
The parameter Goal is not a state, but only a pattern.
In [ ]:
def search(Start, Goal, next_states, heuristic):
Parent = { Start: Start }
Distance = { Start: 0 }
estGoal = heuristic(Start, Goal)
Estimate = { Start: estGoal }
Frontier = Set.Set()
Frontier.insert( (estGoal, Start) )
while not Frontier.isEmpty():
estimate, State = Frontier.pop()
if matches(Goal, State):
print(f'Number of states touched: {len(Distance)}')
return path_to(State, Parent)
stateDist = Distance[State]
for ns in next_states(State):
oldEstimate = Estimate.get(ns, None)
newEstimate = stateDist + 1 + heuristic(ns, Goal)
if oldEstimate == None or newEstimate < oldEstimate:
Parent[ns] = State
Distance[ns] = stateDist + 1
Estimate[ns] = newEstimate
Frontier.insert( (newEstimate, ns) )
if oldEstimate != None:
Frontier.delete( (oldEstimate, ns) )
Given a state and a parent dictionary Parent, the function path_to returns a path leading to the given state.
In [ ]:
def path_to(state, Parent):
p = Parent[state]
if p == state:
return [state]
return path_to(p, Parent) + [state]
Lets draw the start state and animate the solution that has been found.
In [ ]:
def main():
TilesList = [['14', '15'],
['12', '13'],
['10', '11'],
[ '8', '9'],
[ '3', '7'],
[ '2', '6'],
['0', '1', '4', '5']
]
PatternList = intermediate_goals(Goal, TilesList)
State = Start
Solution = []
print('Start state:')
draw_state(Start)
for Pattern in PatternList:
print('Trying to reach the following pattern:')
draw_state(Pattern)
Tiles = find_tiles(Pattern)
ExtendedState = replace_numbers(State, Tiles + ['0'])
Path = search(ExtendedState, Pattern, next_states, manhattan)
MoveList = extract_move_list(Path)
Path = apply_move_list(State, MoveList)
print(f'The following state is reached after {len(Path)-1} steps:');
State = Path[-1]
draw_state(State)
Solution += Path[:-1]
Solution += [ Goal ]
return Solution
In [ ]:
%%time
Path = main()
print(len(Path)-1)
In [ ]:
animation(Path)
In [ ]: